package gold.digger;

import gold.vo.TreeNode;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC110 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        Map<TreeNode, Integer> map = new HashMap<>();
        boolean isBalance = true;

        public boolean isBalanced(TreeNode root) {
            getTreeDepth(root);
            return isBalance;
        }

        public int getTreeDepth(TreeNode root) {
            if (null == root) return 0;
            if (map.containsKey(root)) return map.get(root);
            int leftDepth = getTreeDepth(root.left) + 1;
            int rightDepth = getTreeDepth(root.right) + 1;
            if (Math.abs(rightDepth - leftDepth) > 1) isBalance = false;
            int depth = Math.max(leftDepth, rightDepth);
            map.put(root, depth);
            return depth;
        }
    }

    public void run() {
        Solution solution = new Solution();
        TreeNode rt = TreeNode.createTree("[1,2,2,3,3,null,null,4,4]");
        System.out.println(solution.isBalanced(rt));
    }

    public static void main(String[] args) throws Exception {
        LC110 an = new LC110();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
